Search Results

Documents authored by Li, Meng

Found 3 Possible Name Variants:

Li, Meng

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.47
Streaming Algorithms for Planar Convex Hulls

Authors: Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Many classical algorithms are known for computing the convex hull of a set of n point in R^2 using O(n) space. For large point sets, whose size exceeds the size of the working space, these algorithms cannot be directly used. The current best streaming algorithm for computing the convex hull is computationally expensive, because it needs to solve a set of linear programs. In this paper, we propose simpler and faster streaming and W-stream algorithms for computing the convex hull. Our streaming algorithm has small pass complexity, which is roughly a square root of the current best bound, and it is simpler in the sense that our algorithm mainly relies on computing the convex hulls of smaller point sets. Our W-stream algorithms, one of which is deterministic and the other of which is randomized, have nearly-optimal tradeoff between the pass complexity and space usage, as we established by a new unconditional lower bound.
Cite as

Martín Farach-Colton, Meng Li, and Meng-Tsung Tsai. Streaming Algorithms for Planar Convex Hulls. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{farachcolton_et_al:LIPIcs.ISAAC.2018.47,
  author =	{Farach-Colton, Mart{\'\i}n and Li, Meng and Tsai, Meng-Tsung},
  title =	{{Streaming Algorithms for Planar Convex Hulls}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.47},
  URN =		{urn:nbn:de:0030-drops-99951},
  doi =		{10.4230/LIPIcs.ISAAC.2018.47},
  annote =	{Keywords: Convex Hulls, Streaming Algorithms, Lower Bounds}
}

Meng, Fan-Lin

Document
DOI: 10.4230/OASIcs.ICCSW.2013.81
An Optimal Real-time Pricing Algorithm for the Smart Grid: A Bi-level Programming Approach

Authors: Fan-Lin Meng and Xiao-Jun Zeng

Published in: OASIcs, Volume 35, 2013 Imperial College Computing Student Workshop

Abstract
This paper proposes an improved approach to our previous work [meng2012stackelberg]. [meng2012stackelberg] uses Stackelberg game to model the interactions between electricity retailer and its customers and genetic algorithms are used to obtain the Stackelberg Equilibrium (SE). In this paper, we propose a bi-level programming model by considering benefits of the electricity retailer (utility company) and its customer. In the upper level model, the electricity retailer determines the real-time retail prices with the aim to maximize its profit. The customer reacts to the prices announced by the retailer aiming to minimize their electricity bills in the lower level model. In order to make it more tractable, we convert the hierarchical bi-level programming problem into one single level problem by replacing the lower lever's problem with his Karush–Kuhn–Tucker (KKT) conditions. A branch and bound algorithm is chosen to solve the resulting single level problem. Experimental results show that both the bi-level programming model and the solution method are feasible. Compared with the genetic algorithm approach proposed in work [meng2012stackelberg], the branch and bound algorithm in this paper is more efficient in finding the optimal solution.
Cite as

Fan-Lin Meng and Xiao-Jun Zeng. An Optimal Real-time Pricing Algorithm for the Smart Grid: A Bi-level Programming Approach. In 2013 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 35, pp. 81-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{meng_et_al:OASIcs.ICCSW.2013.81,
  author =	{Meng, Fan-Lin and Zeng, Xiao-Jun},
  title =	{{An Optimal Real-time Pricing Algorithm for the Smart Grid: A Bi-level Programming Approach}},
  booktitle =	{2013 Imperial College Computing Student Workshop},
  pages =	{81--88},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-63-7},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{35},
  editor =	{Jones, Andrew V. and Ng, Nicholas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2013.81},
  URN =		{urn:nbn:de:0030-drops-42752},
  doi =		{10.4230/OASIcs.ICCSW.2013.81},
  annote =	{Keywords: Real-time Pricing, Demand Response, Smart Gird, Bi-level Programming, Branch and Bound Algorithm}
}

Li, Mengdu

Document
DOI: 10.4230/LIPIcs.OPODIS.2016.34
Deletion without Rebalancing in Non-Blocking Binary Search Trees

Authors: Meng He and Mengdu Li

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
We present a provably linearizable and lock-free relaxed AVL tree called the non-blocking ravl tree. At any time, the height of a non-blocking ravl tree is upper bounded by log_d (2m) + c, where d is the golden ratio, m is the total number of successful INSERT operations performed so far and c is the number of active concurrent processes that have inserted new keys and are still rebalancing the tree at this time. The most significant feature of the non-blocking ravl tree is that it does not rebalance itself after DELETE operations. Instead, it performs rebalancing only after INSERT operations. Thus, the non-blocking ravl tree is much simpler to implement than other self-balancing concurrent binary search trees (BSTs) which typically introduce a large number of rebalancing cases after DELETE operations, while still providing a provable non-trivial bound on its height. We further conduct experimental studies to compare our solution with other state-of-the-art concurrent BSTs using randomly generated data sequences under uniform distributions, and find that our solution achieves the best performance among concurrent self-balancing BSTs. As the keys in access sequences are likely to be partially sorted in system software, we also conduct experiments using data sequences with various degrees of presortedness to better simulate applications in practice. Our experimental results show that, when there are enough degrees of presortedness, our solution achieves the best performance among all the concurrent BSTs used in our studies, including those that perform self-balancing operations and those that do not, and thus is potentially the best candidate for many real-world applications.
Cite as

Meng He and Mengdu Li. Deletion without Rebalancing in Non-Blocking Binary Search Trees. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.OPODIS.2016.34,
  author =	{He, Meng and Li, Mengdu},
  title =	{{Deletion without Rebalancing in Non-Blocking Binary Search Trees}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.34},
  URN =		{urn:nbn:de:0030-drops-71032},
  doi =		{10.4230/LIPIcs.OPODIS.2016.34},
  annote =	{Keywords: concurrent data structures, non-blocking data structures, lock-free data structures, self-balancing binary search trees, relaxed AVL trees}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact